package algorithm_demo.demo_advanced;

/**
 * 在中国象棋中马的走法为：日字走法，现给定x和y，以及指定步数为k步，返回有多少中走法
 * x的范围不超过9， y的范围不超过8，x和y组成棋盘
 *
 * @author Api
 * @date 2023/3/26 11:08
 */
public class Test_DP {
    /*暴力递归*/
    public static int way1(int x, int y, int k) {
        return f(x, y, k);
    }

    /**
     * 马从(0,0)出发，有k步要走，并且一定要走完，最终来到x,y位置的方法数是多少？
     *
     * @param x
     * @param y
     * @param k k表示要走的步数
     * @return
     */
    public static int f(int x, int y, int k) {
        //base case 1
        if (k == 0) {
            return x == 0 && y == 0 ? 1 : 0;
        }
        //base case 2
        if (x < 0 || x > 9 || y < 0 || y > 8) {
            return 0;
        }
        return f(x + 2, y - 1, k - 1) + f(x + 2, y + 1, k - 1) + f(x + 1, y + 2, k - 1) + f(x - 1, y + 2, k - 1) + f(x - 2, y + 1, k - 1) + f(x - 2, y - 1, k - 1) + f(x - 1, y - 2, k - 1) + f(x + 1, y - 2, k - 1);
    }

    public static void main(String[] args) {
        int x = 2;
        int y = 3;
        int k = 3;
        System.out.println(way1(x, y, k));
        System.out.println(way2(x, y, k));
        System.out.println(way3(x, y, k));
    }


    /*动态规划*/

    /**
     * 三个动态数组
     *
     * @param x
     * @param y
     * @param k
     * @return
     */
    public static int way2(int x, int y, int k) {
        int[][][] dp = new int[9 + 1][8 + 1][k + 1];
        dp[0][0][0] = 1;
        for (int level = 1; level <= k; level++) {
            //level层，x，y
            for (int i = 0; i < 10; i++) { //x的可能性
                for (int j = 0; j < 9; j++) {//y的可能性
                    dp[i][j][level] =
                            getValue(dp, i + 2, j - 1, level - 1) +
                            getValue(dp, i + 2, j + 1, level - 1) +
                            getValue(dp, i + 1, j + 2, level - 1) +
                            getValue(dp, i - 1, j + 2, level - 1) +
                            getValue(dp, i - 2, j + 1, level - 1) +
                            getValue(dp, i - 2, j - 1, level - 1) +
                            getValue(dp, i - 1, j - 2, level - 1) +
                            getValue(dp, i + 1, j - 2, level - 1);
                }
            }
        }
        return dp[x][y][k];
    }


    public static int getValue(int[][][] dp, int x, int y, int k) {
        if (x < 0 || x > 9 || y < 0 || y > 8) {
            return 0;
        }
        return dp[x][y][k];
    }
    public static int way3(int x, int y, int k){
        return p(0,0,k,x,y);
    }


    //当前来到row，col位置还剩rest步，走完rest步之后，来到x,y位置，方法数多
    public static int p(int row, int col, int rest, int x, int y){
        if (rest == 0){
            return row == x && col == y?1:0;
        }
        if (row < 0 || row >9 || col <0 || col > 8){
            return 0;
        }
        return p(row+2, col - 1, rest-1, x, y)
            +p(row +2, col+1, rest-1, x,y)
            +p(row +1, col+2, rest-1, x,y)
            +p(row -1, col+2, rest-1, x,y)
            +p(row -2, col+1, rest-1, x,y)
            +p(row -2, col-1, rest-1, x,y)
            +p(row -1, col-2, rest-1, x,y)
            +p(row +1, col-2, rest-1, x,y);

    }


}
